#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

struct ListNode
{
    int val;
    struct ListNode* next;
};

struct ListNode* partition(struct ListNode* head, int x)
{
    if (head == NULL)
        return head;
    if (head->next == NULL)
        return head;
    struct ListNode* tail = head;
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    while (tail->next)
    {
        tail = tail->next;
    }
    struct ListNode* newTail = tail;
    while (cur != tail)
    {
        if (cur->val < x)
        {
            prev = cur;
            cur = cur->next;
        }
        else
        {
            if (cur == head)
                head = cur->next;
            else
                prev->next = cur->next;
            newTail->next = cur;
            newTail = cur;
            cur = cur->next;
            newTail->next = NULL;
        }
    }
    if (cur->val >= x)
    {
        if (cur == head)
            head = cur->next;
        else if (tail->next != NULL)
            prev->next = cur->next;
        else
            return head;
        newTail->next = cur;
        cur->next = NULL;
    }
    return head;
}

int main()
{
    return 0;
}